#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
using namespace std;

void quickSort(vector<int>& arr, int left, int right)
{
	if (left >= right) return;

	int keyi = left;
	int begin = left, end = right;
	while (begin < end)
	{
		while (begin < end && arr[end] >= arr[keyi]) end--;
		while (begin < end && arr[begin] <= arr[keyi]) begin++;
		swap(arr[begin], arr[end]);
	}
	swap(arr[keyi], arr[begin]);

	quickSort(arr, left, end - 1);
	quickSort(arr, begin + 1, right);
}

int main()
{
	vector<int> arr({ 5,6,8,9,5,3,2,5,1,4,7 });
	int n = arr.size();
	quickSort(arr, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << " ";
	}

	return 0;
}